import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    //
    public static int n, m;
    public static int x1, y1, x2, y2;
    public static int[][] dist;
    public static int[][] cnt;
    public static int[] dx = {0,0,1,-1};
    public static int[] dy = {1,-1,0,0};

    public static int bfs(int[][] CityMap){
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x1, y1});
        dist[x1][y1] = 0;
        cnt[x1][y1] = 1;

        while(!q.isEmpty()){
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for(int k = 0; k < 4; k++){
                int x = a + dx[k], y = b + dy[k];
                if(x >= 0 && x < n && y >= 0 && y < m && CityMap[x][y] != -1){
                    if(dist[x][y] == -1){  //第一次到达这个位置
                        dist[x][y] = dist[a][b] + 1;
                        cnt[x][y] += cnt[a][b];
                        q.offer(new int[]{x, y});
                    }else{                //不是第一次到达这个位置
                        if(dist[a][b] + 1 == dist[x][y]){  //判断是否是最短路到达 [x, y]
                            cnt[x][y] += cnt[a][b];
                        }
                    }
                }
            }
        }
        return cnt[x2][y2];
    }

    public int CountPath(int[][] CityMap, int _m, int _n){
        n = _n; m = _m;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                dist[i][j] = -1;
                if(CityMap[i][j] == 1) {
                    x1 = i;
                    y1 = j;
                }else if(CityMap[i][j] == 2){
                    x1 = i;
                    y1 = j;
                }
            }
        }
        return bfs(CityMap);
    }

    //
    public int maxProfit (int[] prices, int k) {
        int n = prices.length;

        int[][] f = new int[n][k + 1];
        int[][] g = new int[n][k + 1];
        k = Math.min(k, n / 2);

        for(int i = 0; i <= k; i++){
            f[0][i] = g[i][0] = -0x3f3f3f3f;
        }
        f[0][0] = -prices[0];
        g[0][0] = 0;

        for(int i = 1; i < n; i++){
            for(int j = 0; j <= k; j++){
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j >= 1) { g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);}
            }
        }

        int ret = 0;
        for(int j = 0; j <= k; j++){
            ret = Math.max(ret, g[n - 1][j]);
        }
        return ret;
    }
}
